题解 P3556 【[POI2013]MOR-Tales of seafaring】

发表于 | 更新于

$Description$

给$n$个点$m$条边无向图，每次询问两个点之间是否有长度为$d$的路径（不一定是简单路径）

$Solution$

设这两个点分别为$x,y$

如果$x,y$之间有一条奇偶性与$d$相同且长度$\leqslant d$的路径，那么结果就是$TAK,$否则则是$NIE.$

证明$:$对于一条边$(a,b)$,可以花费$2$的长度,从$a$到$b$，再从$b$到$a$.那么对于一条长度$\leqslant d$且奇偶性与$d$相同的路径, 我们可以在一条边上反复横跳以能够刚好以$d$的长度到达终点。

由于边权为$1,$所以求最短路可以用$bfs$

$Code$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#include <bits/stdc++.h>
#define ll long long
#define inf 0x3f3f3f3f
#define re register
#define N 100057
using namespace std;
struct edge{
    int to,next;
}e[N];
struct node{
    int y,d,id;
};
inline int read(){
    int x=0,w=0;char ch=getchar();
    while (!isdigit(ch))w|=ch=='-',ch=getchar();
    while (isdigit(ch))x=(x<<1)+(x<<3)+ch-'0',ch=getchar();
    return w?-x:x;
}
int n,m,Q,dis[N],cnt,head[N];
bool ans[1050596];
vector<node>v[N];
inline void add(int u,int v){
    e[++cnt].to=v;
    e[cnt].next=head[u];
    head[u]=cnt;
    e[++cnt].to=u;
    e[cnt].next=head[v];
    head[v]=cnt;
}
void bfs(int s){
    queue<int>q;
    q.push(s);
    for (int i=1;i<=n+n;++i)dis[i]=0;
    while (!q.empty()){
        int u=q.front();q.pop();
        for (int i=head[u];i;i=e[i].next){
            int v=e[i].to;
            if (dis[v])continue;
            dis[v]=dis[u]+1;
            q.push(v);
        }
    }
    for (int i=0;i<v[s].size();++i){
        node p=v[s][i];
        int t=dis[p.y+(p.d&1)*n];
        ans[p.id]=(t<=p.d&&t&&((t&1)==(p.d&1)));
    }
}
signed main(){
    n=read(),m=read(),Q=read();
    for (int i=1;i<=m;++i){
        int u=read(),v=read();
        add(u+n,v);add(u,v+n);
    }
    for (int i=1;i<=Q;++i){
        int x=read(),y=read(),d=read();
        v[x].push_back((node){y,d,i});
    }
    for (int i=1;i<=n;++i)
        bfs(i);
    for (int i=1;i<=Q;++i)
        puts(ans[i]?"TAK":"NIE");
    return 0;
}